package com.wcj.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class 前中后层次非递归遍历 {

    static void PreOrderNonRecursive(TreeNode root){
        if (root == null){
            return;
        }
        Stack<TreeNode> S = new Stack<>();

        while (true){
            while (root != null){
                System.out.println(root.val);
                S.push(root);
                root = root.left;
            }
            if (S.isEmpty()){
                break;
            }
            root = S.pop();
            root = root.right;
        }

    }


    static void InOrderNonRecursive(TreeNode root){
        if (root == null){
            return;
        }
        Stack<TreeNode> S = new Stack<>();
        while (true){
            while (root != null){
                S.push(root);
                root = root.left;
            }
            if (S.isEmpty())
                break;
            root = S.pop();
            System.out.println(root.val);
            root = root.right;
        }

    }

    static void PostOrderNonRecursive(TreeNode root){
        Stack<TreeNode> S = new Stack<>();
        while (true){
            if (root != null){
                S.push(root);
                root = root.left;
            }else {
                if (S.isEmpty()){
                    return;
                }else {
                    if (S.peek().right == null){
                        root = S.pop();
                        System.out.println(root.val);
                        if (root == S.peek().right){
                            System.out.println(S.peek().val);
                            S.pop();
                        }
                    }
                    if (!S.isEmpty()){
                        root = S.peek().right;
                    }else root = null;
                }
            }
        }
    }

    static void LevelOrder(TreeNode root){
        TreeNode tmp;
        Queue<TreeNode> Q = new LinkedList<>();
        if (root == null)return;
        Q.offer(root);
        while (!Q.isEmpty()){
            tmp = Q.poll();
            System.out.println(tmp.val);
            if (tmp.left != null){
                Q.offer(tmp.left);
            }
            if (tmp.right != null){
                Q.offer(tmp.right);
            }
        }

    }
}
